/*
 * WA
 * DP
 * knapsack problem
 * Wrong Answer
 * I need more test case
 **/
#include <stdio.h>
#include <string.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int N[10][2];
int f[10][100000];
int knapsack_max(int x, int v);
int main(int argc, char **argv)
{
	int cash, n, i;
	while (scanf("%d%d", &cash, &n) != EOF) {
		for (i = 0; i < n; i++) {
			if ((scanf("%d", &N[i][0]) != 1) || (scanf("%d", &N[i][1]) != 1))
				return 0;
		}
		memset(f, 0, sizeof(int) * cash * n);
		printf("%d\n", knapsack_max(n - 1, cash));
	}
	return 0;
}

int knapsack_max(int x, int v)
{
	int t, t1, t2, t3, j;
	
	if (x < 0)
		return 0;
	if (x == 0) {
		t = N[x][0] * N[x][1];
		f[x][v] = v >= t? t: ((v / N[x][1]) * N[x][1]);
		return f[x][v];
	}
	if (f[x][v] > 0)
		return f[x][v];
	t1 = knapsack_max(x - 1, v);
	f[x][v] = max(f[x][v], t1);
	for (j = 1; j <= N[x][0]; j++) {
		t3 = v - j * N[x][1];
		if (t3 < 0)
			break;
		t2 = knapsack_max(x - 1, t3) + j * N[x][1];
		f[x][v] = max(f[x][v], t2);
	}
	return f[x][v];
}
